package com.bo.day20231123;

import java.util.Arrays;

/**
 *  翻转对
 * https://leetcode.cn/problems/reverse-pairs/description/
 * 一个数组中,当左边的数大于右边的数*2
 * 例如：
 * arr={2,4,3,0,9,1,8,6,5,2}
 * 2：(0*2) 1个
 * 4：(0*2),(1*2) 2个
 * 3：(0*2),(1*2) 2个
 * 0： 0个
 * 9：(0*2),(1*2) 2个
 * 1： 0个
 * 8：(1*2) 1个
 * 6：(1*2) 1个
 * 5：(1*2) 1个
 * 2：0个
 * 1+2+2+0+2+0+1+1+1+0=10
 *
 * @Author: gpb
 * @Date: 2023/11/27 14:31
 * @Description:
 */
public class BiggerThanRightTwice {

    public static void main (String[] args) {
//        System.out.println(1 << 1);
//        System.out.println(-5 << 1);
//        System.out.println(2 < (1 * 2));
        int[] arr = {5, 1, 3, 0, 9, 1, 8, 6, 5, 2};
        System.out.println(biggerThanRightTwice(arr));
        System.out.println(Arrays.toString(arr));
    }

    public static int biggerThanRightTwice (int[] arr) {
        if (arr == null || arr.length <= 2) {
            return 0;
        }
        return process(arr, 0, arr.length - 1);
    }

    public static int process (int[] arr, int l, int r) {
        if (l == r) {
            return 0;
        }
        int mid = l + ((r - l) >> 1);
        return process(arr, l, mid) + process(arr, mid + 1, r) + merge(arr, l, mid, r);
    }

    public static int merge (int[] arr, int l, int mid, int r) {
        int ans = 0;
        // [l...mid],[mid+1...r]
        // 左边数组起点
        int lBegin = l;
        // 右边数组起点
        int rBegin = mid + 1;
        for (; lBegin <= mid; lBegin++) {
            // arr[lBegin] > arr[rBegin] << 1 等于 arr[lBegin] > arr[rBegin] * 2
            while (rBegin <= r && arr[lBegin] > arr[rBegin] << 1) {
                rBegin++;
            }
            // 为什么要减1呢？
            // 例如：arr = {5, 1, 3, 0, 9, 1, 8, 6, 5, 2};l=0,mid=0,r=1
            //  lBegin=l=0,rBegin=mid+1=0+1;
            //  rBegin<=r 成立&&arr[lBegin]>arr[rBegin]<<1 成立 5 > 1*2成立
            // rBegin++;rBegin=2;
            // 数组范围是 0  1
            // 如果不减1,就会超了,因为数组比较范围下标0-1就两位数,最大情况是1
            ans += rBegin - mid + 1;
        }
        // 开始排序
        int[] help = new int[r - l + 1];
        int i = 0;
        int p1 = l;
        int p2 = mid + 1;
        while (p1 <= mid && p2 <= r) {
            help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }
        while (p1 <= mid) {
            help[i++] = arr[p1++];
        }
        while (p2 <= r) {
            help[i++] = arr[p2++];
        }
        for (i = 0; i < help.length; i++) {
            arr[l + i] = help[i];
        }
        return ans;
    }
}
